package a_doubleWrite;

/**
 * 211. 添加与搜索单词 - 数据结构设计
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 *
 * 实现词典类 WordDictionary ：
 *
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。
 * word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
 * @author luolidong
 * @version 1.0
 * @create 2021-07-31 09:54
 */
public class L211 {
    private class Trie {
        boolean isEnd;
        Trie[] next;

        public Trie() {
            this.isEnd = false;
            this.next = new Trie[26];
        }
    }

    private Trie root;

    public L211() {
        root = new Trie();
    }

    public void addWord(String word) {
        Trie node = root;
        for (char c : word.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new Trie();
            }
            node = node.next[c - 'a'];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = root;
        return dfs(node, 0, word);
    }

    private boolean dfs(Trie node, int index, String word) {
        if (index == word.length()) {
            return node.isEnd;
        }
        char c = word.charAt(index);
        if (c == '.') {
            //遍历下一个节点，看能不能找到匹配的
            for (Trie t : node.next) {
                if (t != null && dfs(t, index + 1, word)) {
                    return true;
                }
            }
        } else {
            if (node.next[c - 'a'] == null) {
                return false;
            } else {
                return dfs(node.next[c - 'a'], index + 1, word);
            }
        }
        return false;
    }
}
